The present invention generally relates to parity generating circuits, and more particularly to a parity generating circuit for generating parities of a Reed Solomon code.
When carrying out data transmission such as in data communication, PCM recording and reproducing apparatuses, digital audio discs and the like, an error correction is conventionally carried out so as to correctly restore the transmitted data. In order to carry out such an error correction, parities (check vectors) which are generated according to a predetermined method are added to the data which are to be transmitted so as to constitute blocks, and the signal transmission or recording is carried out in such blocks. A code error in the blocks which are received or reproduced is corrected by use of the parities.
Various kinds of error correction codes comprising the parities and the data which are to be transmitted and are also generating elements of the parities are known. Out of the known error correction codes, the Reed Solomon code is popularly used because of its superior error correction capability and the redundancy of the transmitted information (that is, the ratio between the parities and the data in the block).
First, description will be given with respect to the general principle of generating the Reed Solomon code. A Reed Solomon code having a code word (block) with a word length n, k data (data vectors) which are to be transmitted, and (n-k) parities (check vectors) is often referred to as a (n, k) Reed Solomon code, where n and k are natural numbers. The code word of this (n, k) Reed Solomon code can be described by the following row matrix W of equation (1), where C.sub.1 through C.sub.n are data or parity and there are at least one data and one parity. EQU W=[C.sub.1, C.sub.2, . . . , C.sub.n ] (1)
In addition, C.sub.1 through C.sub.n are m-bit vectors, respectively, and are elements in a Galois Field GF(2.sup.m) in the Reed Solomon code defined in GF(2.sup.m). It is known that the following condition (2) must be satisfied between m and n. EQU 2.sup.m -1.gtoreq.n (2)
When a check matrix H.sub.0 is assumed to be a (n-k) row by n column matrix described by the following equation (3), where .alpha. denotes a primitive element of GF(2.sup.m), the parities are generated so that a syndrome S described by the following equation (4) can be described as a column matrix comprising (n-k) zero vectors, where T in equation (4) denotes a transposed matrix. ##EQU1## A parity generating polynomial G(x) of the (n, k) Reed Solomon code of the code word W described by the following equation (5) can be described by the following equation (6), where D.sub.1 through D.sub.k denote data and P.sub.k+1 through P.sub.n denote parities in the equation (5). EQU W=[D.sub.1, D.sub.2, . . . , D.sub.k, P.sub.k+1, P.sub.k+2, . . . , P.sub.n ] (5) EQU G(x)=(x-1).multidot.(x-.alpha.).multidot.(x-.alpha..sup.2).multidot. . . . (x-.alpha..sup.n-k-1) (6)
The following equation (7) can be obtained by expanding the equation (6), where a.sub.1 through a.sub.n-k are coefficients which can be described by the primitive EQU G(x)=x.sup.n-k +a.sub.1 .multidot.x.sup.n-k-1 +a.sub.2 .multidot.x.sup.n-k-2 +a.sub.n-k-1 .multidot.x+a.sub.n-k ( 7)
When the data [D.sub.1, D.sub.2, . . . , D.sub.k ] within the code word W are used to define a polynomial F.sub.D (x) which is described by the following equation (8), a remainder polynomial R(x) which is obtained when the polynomial F.sub.D (x) is divided by the parity generating polynomial G(x) can be described by the following equation (9). EQU F.sub.D (x)=D.sub.1 .multidot.x.sup.n-1 +D.sub.2 .multidot.x.sup.n-2 +. . . +D.sub.k .multidot.x.sup.n-k ( 8) EQU R(x)=R.sub.1 .multidot.x.sup.n-k-1 +R.sub.2 .multidot.x.sup.n-k-2 +. . . +R.sub.n-k-1 .multidot.x+R.sub.n-k ( 9)
A product F(x) of the quotient in this case and the parity generating polynomial G(x) can be described by F(x)=F.sub.D (x)-R(x), but this subtraction is a modulo-2 subtraction which is the same as a modulo-2 addition. Accordingly, the product F(x) can be described by F(x)=F.sub.D (x)+R(x), and the product F(x) described by the following equation (10) is divisible by the parity generating polynomial G(x). ##EQU2## Accordingly, from the equation (10), it can be seen that the parities P.sub.k+1 and P.sub.k+2, . . . , P.sub.n in the Reed Solomon code described by the equation (5) can be described by the following set of equations (11).
There are conventional circuits for generating the parities of the Reed Solomon code according to the generating principle described heretofore. In first and second easily conceivable circuits which will be described later on in the present specification in conjunction with the drawings, when the code word W.sub.0 consists of parities P.sub.i+1 through P.sub.j-1 and data D.sub.0 through D.sub.i and data D.sub.j through D.sub.n comprising the elements of GF(2.sup.m) as described by the following equation (12), there is a problem in that the parities P.sub.i+1 through P.sub.j-1 cannot be generated for a code word W.sub.0 in which the parities P.sub.i+1 through P.sub.j-1 are between the data D.sub.1 through D.sub.i and the data D.sub.j through D.sub.n. In the equation (12), n-k=j-i-1 and n&gt;j&gt;i. EQU W.sub.0 =[D.sub.1, D.sub.2, . . . , D.sub.i, P.sub.i+1, . . . , P.sub.j-1, D.sub.j, . . . , D.sub.n ] (12)
As will be described later on in the present specification in conjunction with the drawings, there is a third easily conceivable circuit for generating the parities by use of a parity generating matrix and a fourth easily conceivable circuit for generating the parites by use of simultaneous equations, even when the code word W.sub.0 is described by the equation (12) and the parities P.sub.i+1 through P.sub.j-1 are between the data D.sub.1 through D.sub.i and the data D.sub.j through D.sub.n.
However, according to the third conceivable circuit, there is are problems in that a read only memory (ROM) must be used to store each element of the parity generating polynomial because the parity generating matrix has no regularity, and each coefficient multiplier of the third conceivable circuit must be constructed so that it is possible to multiply any kind of coefficient since the coefficients from the ROM successively change depending on the input data. As a result, the scale of the third conceivable circuit as a whole becomes large and the circuit is expensive.
On the other hand, each coefficient multiplier of the fourth conceivable circuit always multiplies a constant coefficient to an input signal, and the construction of the coefficient multiplier can be simplified compared to that of the third conceivable circuit. However, there is a problem in that when substitutions are made into the simultaneous equations so as to generate the parities P.sub.i+1 through P.sub.j-1, it is necessary to carry out an extremely large number of operation steps by use of an arithmetic logic unit (ALU), for example.